#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct ListNode 
{
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) 
	{

	}
};
class Solution 
{
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
	{
		if (l1 == nullptr && l2==nullptr)
		{
			return nullptr;
		}
		else if (l1 == nullptr && l2)
		{
			return l2;
		}
		else if (l2 == nullptr && l1)
		{
			return l1;
		}
		else
		{
			vector<int> vec;

			ListNode* p = l1;
			while (p->next)
			{
				vec.push_back(p->val);
				p = p->next;
			}
			vec.push_back(p->val);
			p->next = l2;
			ListNode* t = l2;
			while (t->next)
			{
				vec.push_back(t->val);
				t = t->next;
			}
			vec.push_back(t->val);

			sort(vec.begin(), vec.end());

			p = l1;
			int i = 0;
			while (p->next)
			{
				p->val = vec[i++];
				p = p->next;
			}
			p->val = vec[i];
			return l1;
		}
	}
};

int main()
{
	ListNode a1(2);
	ListNode a2(1);
	ListNode b1(4);
	ListNode b2(3);
	a1.next = &a2;
	b1.next = &b2;

	Solution s;
	
	ListNode* p=s.mergeTwoLists(&a1, &b1);
	while (p->next)
	{
		cout << p->val << endl;
		p = p->next;
	}
	cout << p->val << endl;
	return 0;
}